import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with Intellij JDEA
 * Description:
 * User:
 * Date:2022-03-20
 * Time:18:20
 */
public class TestDemo {


    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH = maxDepth(root.left);
        int leftR = maxDepth(root.right);
        return leftH > leftR ? leftH+1 : leftR+1;
    }
    /**
     * 判断一棵树 是不是高度平衡的二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);
        return Math.abs((leftH - rightH)) <=1 && isBalanced(root.left) && isBalanced(root.right);
    }



    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null && subRoot != null || root != null && subRoot == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node.val==subRoot.val){
                if(isSameTree(node,subRoot)){
                    return true;
                }
            }
            if (node.left!=null){
                queue.add(node.left);
            }
            if (node.right!=null){
                queue.add(node.right);
            }
        }
        return false;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p != null && q == null  || p == null && q!= null) {
            return false;
        }
        if(p == null && q == null) {
            return true;
        }
        //p != null && q!= null
        if(p.val != q.val) {
            return false;
        }
        //p != null && q!= null  && p.val == q.val
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }


    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.pop());
        System.out.println(myStack.peek());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.empty());
    }
}
